package com.tlvip.arithmetic.ch08;

import java.util.Arrays;

/**
 * <p>description：快速排序</p>
 * <p>copyright： copyright(C)2016-2099</p>
 * <p>Life is short,we need passion</p>
 * <p>Summary： </p>
 * <p>instructions： </p>
 * Date 1/27/21</p>
 * Author mac
 *
 * @version 1.0
 */
public class QuickSort {

    public static void main(String[] args) {
        int data[] = {5, 3, 7, 8, 2, 9, 4};
        quickSort(data, 0, data.length - 1);
        System.out.println(Arrays.toString(data));
    }

    // 时间复杂度 O(n^2)
    // 空间复杂度 O(n)
    // 不稳定排序
    public static void quickSort(int data[], int left, int right) {
        int base = data[left];
        int ll = left;
        int rr = right;
        while (ll < rr) {
            while (ll < rr && data[rr] >= base) {
                rr--;
            }
            // 表示找到有比右侧大的
            if (ll < rr) {
                int temp = data[rr];
                data[rr] = data[ll];
                data[ll] = temp;
                ll++;
            }
            while (ll < rr && data[ll] <= base) {
                ll++;
            }
            if (ll < rr) {
                int temp = data[rr];
                data[rr] = data[ll];
                data[ll] = temp;
                rr--;
            }
        }
        // 递归分成三部分，左右继续快排
        if (left < ll) {
            quickSort(data, left, ll - 1);
        }
        if (ll < right) {
            quickSort(data, ll + 1, right);
        }
    }
}
